package com.atguigu.linkedlist;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //测试
        //先创建节点
        HeroNode hero1 = new HeroNode(1,"宋江","及时雨") ;
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟") ;
        HeroNode hero3 = new HeroNode(3,"吴用","智多星") ;
        HeroNode hero4 = new HeroNode(6,"林冲","豹子头") ;
        HeroNode hero5 = new HeroNode(13,"鲁智深","花和尚") ;
        //创建链表
        SingleLinkedList linkedList = new SingleLinkedList() ;
        linkedList.add(hero1);
        linkedList.add(hero2);
        linkedList.add(hero3);
        linkedList.add(hero4);
        linkedList.add(hero5);
        linkedList.list();
        System.out.println("链表反转后");
        //SingleLinkedList.reverseList(linkedList.getHead());

        //测试反转
        /*//测试删除
        linkedList.add(hero1);
        linkedList.add(hero2);
        linkedList.add(hero3);
        linkedList.add(hero4);
        linkedList.add(hero5);
        linkedList.list();
        System.out.println("删除后--------------");
        linkedList.delete(new HeroNode(32,"杨雄","病关索"));
        linkedList.delete(hero5);
        linkedList.list();*/
       /* //测试插入
        linkedList.insert(hero5);
        linkedList.insert(hero2);
        linkedList.insert(hero3);
        linkedList.insert(hero1);
        linkedList.insert(hero4);
        linkedList.insert(hero4);
        linkedList.list();*/
       /* //测试修改链表节点
        linkedList.update(new HeroNode(13,"花荣","小李广"));
        //测试显示链表
        System.out.println("修改后链表----------------");
        linkedList.list();*/
    }
}

//定义SingleLinkedList来管理英雄
class SingleLinkedList {
    //定义头节点
    private HeroNode head = new HeroNode(0,"","") ;

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    //链表添加节点
    public void add(HeroNode heroNode) {
        //先找到末节点,定义临时变量tmp
        HeroNode tmp = head ;
        while (true) {
            if (tmp.next == null) {
                break; //找到链表的最后
            }
            //没有找到，将tmp指针后移
            tmp = tmp.next ;
        }
        //退出while循环，tmp就指向了最后节点
        tmp.next = heroNode ;
    }

    //显示链表
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("当前链表为空");
            return;
        }
        //因为头结点不能动，借助辅助变量tmp其实就是指针来遍历
        HeroNode tmp = head.next ;
        while (true) {
            //判断是否到链表最后
            if (tmp == null) {
                break;
            }
            //输出节点信息
            System.out.println(tmp);
            //tmp后移
            tmp = tmp.next ;
        }
    }

    /**插入新节点步骤：
     * 1.找到新节点的位置，通过辅助变量（指针），遍历来搞定
     * 2.newHeroNode.next == tmp.next
     * 3.tmp.next == newHeroNode
     */
    public void insert(HeroNode heroNode) {
        HeroNode tmp = head ;
        boolean flag = false ; //no是否存在
        while (true) {
            if (tmp.next == null) {
                break; //链表查完未找到
            }
            if (tmp.next.no > heroNode.no) {
                break;
            }  else if (tmp.next.no == heroNode.no) {
                flag = true ;
                break;
            }
            tmp = tmp.next ;
        }
        if (flag) {
            System.out.printf("准备插入的英雄编号 %d 已存在,不能插入\n",heroNode.no);
        } else {
            //插入heroNode
            heroNode.next = tmp.next ;
            tmp.next = heroNode ;
        }
    }

    //根据编号no来修改链表
    public void update(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //定义一个辅助变量
        HeroNode tmp = head.next ;
        boolean flag = false ; //flag来表明是否找到对应no
        while (true) {
            if (tmp == null) {
                break; //已经遍历完链表
            }
            if (tmp.no == newHeroNode.no) {
                flag = true ;
                break ;
            }
            tmp = tmp.next ;
        }
        //根据flag判断是否需要修改
        if (flag) {
            System.out.printf("找到了编号为 %d 的节点,已经修改\n",newHeroNode.no);
            tmp.name = newHeroNode.name ;
            tmp.nickname = newHeroNode.nickname ;
        } else {
            System.out.printf("没有找到编号为 %d 的节点,不能修改\n",newHeroNode.no);
        }
    }

    /**删除节点步骤
     * 1.查找删除节点前一个节点
     * 2.tmp.next = tmp.next.next(删除的节点没有其他节点指向会被垃圾回收机制回收掉)
     */
    public void delete(HeroNode heroNode) {
        HeroNode tmp = head ;
        boolean flag = false ; //是否找到删除节点
        while (true) {
            if (tmp.next == null) {
                break; //未找到
            }
            if (tmp.next.no == heroNode.no) {
                flag = true ;
                break;
            }
            tmp = tmp.next ;
        }
        if (flag) {
            tmp.next = tmp.next.next ;
        } else {
            System.out.printf("未找到英雄编号%d的节点,不能删除\n",heroNode.no);
        }
    }

    //求单链表中有效节点的个数
    public static int getValidNode(HeroNode head) {
        if (head.next == null) {
            return 0 ;
        }
        int count = 0 ;
        HeroNode curr = head.next ;
        while (curr != null) {
            count++ ;
            curr = curr.next ;
        }
        return count ;
    }

    //腾讯面试题：反转单链表
    public static void reverseList(HeroNode head) {
        if (head.next == null | head.next.next == null) {
            System.out.println("无需反转");
            return;
        }
        HeroNode curr = head.next ; //辅助变量（指针）用于遍历
        HeroNode next = null ;//指向当前节点curr的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","") ;
        while (curr != null) {
            next = curr.next ;
            curr.next = reverseHead.next ;
            reverseHead.next = curr.next ;
            curr = next ;
        }
        head.next = reverseHead.next ;
    }

}

//定义HeroNode，每个HeroNode对象就是一个节点
class HeroNode {
    public int no ;
    public String name ;
    public String nickname ;
    public HeroNode next ; //指向下一个节点

    //构造器
    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
